package leetcode.每日一题;

import org.junit.Test;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author :songyaozhang
 * @date :Created 2021/8/6 9:42
 * @description :https://leetcode-cn.com/problems/shortest-path-visiting-all-nodes/
 */
public class 访问所有节点的最短路径 {
    @Test
    public void test() {
        Solution solution = new Solution();
        solution.shortestPathLength(new int[][]{{1,2,3},{0},{0},{0}});
    }

    class Solution {
        public int shortestPathLength(int[][] graph) {
            int n = graph.length;
            int[] inDeg = new int[n];
            for (int[] ints : graph) {
                for (int anInt : ints) {
                    inDeg[anInt]++;
                }
            }
            Queue<Integer> queue = new LinkedList<>();
            for (int i = 0; i < inDeg.length; i++) {
                if (inDeg[i] == 0) {
                    queue.offer(i);
                }
            }
            while (!queue.isEmpty()) {
                Integer cur = queue.poll();
                for (int i = 0; i < graph[cur].length; i++) {
                    if (--inDeg[graph[cur][i]] == 0) {
                        queue.offer(i);
                    }
                }
            }
            ArrayList<Integer> ans = new ArrayList<>();
            for (int i = 0; i < inDeg.length; i++) {
                if (inDeg[i] == 0) {
                    ans.add(i);
                }
            }
            System.out.println(ans);
            return 0;
        }
    }


}
